﻿using System;
using System.Collections.Generic;
using System.Linq;

using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.Trees
{
    public class ParentReferenceTree<T> : IRootedTree<T>
        where T : IEquatable<T>
    {
        private readonly IMap<T, T> _parent;
        private readonly T _root;
        private readonly T _token;
        private readonly Func<IEnumerable<KeyValuePair<T, T>>, IMap<T, T>> _createMap;
        private readonly EqualityComparison<T> _equalityComparison;

        public ParentReferenceTree(IEnumerable<KeyValuePair<T, T>> items = null, EqualityComparison<T> equalityComparison = null,
            Func<IEnumerable<KeyValuePair<T,T>>,IMap<T,T>> createMap=null, T token = default(T))
        {
            items = items ?? Enumerable.Empty<KeyValuePair<T, T>>();
            _createMap = createMap ?? (values => AlgoritmiaFactory.Maps<T, T>.BuildDefault(values));
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            _token = token;
            _parent = _createMap(items);
            _root = _parent.Keys().First();
            foreach(var key in _parent.Keys())
            {
                if (_equalityComparison(key,_parent[key]) && !IsToken(key))
                {
                    _root = key;
                    break;
                }
            }
        }

        public ParentReferenceTree(T root, IEnumerable<KeyValuePair<T, T>> items = null, EqualityComparison<T> equalityComparison = null,
            Func<IEnumerable<KeyValuePair<T,T>>,IMap<T,T>> createMap=null, T token = default(T))
        {
            items = items ?? Enumerable.Empty<KeyValuePair<T, T>>();
            _createMap = createMap ?? (values => AlgoritmiaFactory.Maps<T, T>.BuildDefault(values));
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            _parent = _createMap(items);
            _root = root;
            _token = token;
        }
        #region IRootedTree<T> Members

        public T Root
        {
            get { return _root; }
        }

        public IEnumerable<T> Successors(T node)
        {
            if (IsToken(node))
            {
                yield break;
            }

            foreach (var key in _parent.Keys())
            {
                if (_equalityComparison(_parent[key],node) && !IsToken(key) && !IsRoot(key))
                    yield return key;
            }
        }

        
        public IEnumerable<T> Predecessors(T node)
        {
            T v;
            try
            {
                v = _parent[node];
            }
            catch(KeyNotFoundException)
            {
                yield break;
            }
            if (!_equalityComparison(node,v))
                yield return _parent[node];
        }

        public int InDegree(T node)
        {
            return IsRoot(node) || IsToken(node) ? 0 : 1;
        }

        public int OutDegree(T node)
        {
            return Successors(node).Count();
        }

        public IEnumerable<IRootedTree<T>> SubTrees()
        {
            foreach(var item in Successors(_root))
            {
                yield return Tree(item);
            }
        }

        public IRootedTree<T> Tree(T root)
        {
            IMap<T, T> tmpMap = _createMap(new[] {new KeyValuePair<T, T>(root, root)});
            foreach(var successor in Successors(root))
            {
                FillTree(tmpMap, successor);
                tmpMap[successor] = root;
            }
            return new ParentReferenceTree<T>(root, tmpMap);
            //return new ParentReferenceTree<T>(root,null, values => _parent);
        }

        #endregion

        private void FillTree(IMap<T, T> map, T value)
        {
            foreach (var successor in Successors(value))
            {
                FillTree(map, successor);
                map[successor] = value;
            }
        }

        public override string ToString()
        {
            return String.Format("{0} <{1}> root = {2} nodes = {3}", GetType().Name, typeof (T).Name, _root, _parent);
        }

        #region Helper Methods

        private bool IsToken(T item)
        {
            return _equalityComparison(item, _token);
        }

        private bool IsRoot(T item)
        {
            return _equalityComparison(_root, item);
        }

        #endregion
    }
}
